package practice;

import java.util.*;

public class Day32 {

    //总路径和
    private Map<Long,Integer> map;
    public int pathSum(TreeNode root, int targetSum) {
        map = new HashMap<>();
        map.put(0L,1);
        return rootSum(root,0,targetSum);
    }

    private int rootSum(TreeNode root,long sum,int targetSum) {
        if(root == null) {
            return 0;
        }
        sum += root.val;
        int ret = 0;
        ret += map.getOrDefault(sum-targetSum,0);
        map.put(sum,map.getOrDefault(sum,0)+1);
        ret += rootSum(root.left,sum,targetSum);
        ret += rootSum(root.right,sum,targetSum);
        map.put(sum,map.getOrDefault(sum,0)-1);
        return ret;
    }
    //和为k的数组
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int ret = 0;
        for(int x : nums) {
            count += x;
            ret += map.getOrDefault(count-k,0);
            map.put(count,map.getOrDefault(count,0)+1);
        }
        return ret;
    }
    //螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new LinkedList<>();
        if (matrix == null || matrix.length == 0) {
            return list;
        }
        int n = matrix.length;
        int m = matrix[0].length;
        int top = 0;
        int bottom = n - 1;
        int left = 0;
        int right = m - 1;
        while (left <= right && top <= bottom) {
            // 第一行
            for (int i = left; i <= right; i++) {
                list.add(matrix[top][i]);
            }
            // 最后一列
            for (int i = top + 1; i <= bottom; i++) {
                list.add(matrix[i][right]);
            }
            // 最后一行
            for (int i = right - 1; i >= left; i--) {
                list.add(matrix[bottom][i]);
            }
            // 第一列
            for (int i = bottom - 1; i > top; i--) {
                list.add(matrix[i][left]);
            }
            left++;
            top++;
            right--;
            bottom--;
        }
        return list;
    }
    
    //判断字符是否唯一
    public boolean isUnique(String astr) {
        Set<Character> set = new HashSet<>();
        if(astr.length() == 0) {
            return true;
        }
        set.add(astr.charAt(0));
        for(int i = 1; i < astr.length(); i++) {
            if(set.contains(astr.charAt(i))) {
                return false;
            }
            set.add(astr.charAt(i));

        }
        return true;
    }
    //漂亮数组（分治，递归）
    Map<Integer,int[]> map1 = new HashMap<>();
    public int[] beautifulArray(int n) {
        return fun(n);
    }
    private int[] fun(int n) {
        if(map.containsKey(n)) {
            return map1.get(n);
        }
        int[] ret = new int[n];
        if(n == 1) {
            ret[0] = 1;
        }else {
            int k = 0;
            for(int i : fun((n+1)/2)) {
                ret[k++] = 2 * i-1;
            }
            for(int i : fun(n/2)) {
                ret[k++] = 2 * i;
            }
        }
        map1.put(n,ret);
        return ret;
    }
    //递归乘法
    public int multiply(int A, int B) {
        if(B == 0) {
            return 0;
        }
        return A + multiply(A,B-1);
    }
    //判断字符是否唯一（位运算）
    public boolean isUnique1(String astr) {
        int i = 0;
        for(char ch : astr.toCharArray()) {
            int k = ch - 'a';
            if((i & (1 << k)) != 0) {
                return false;
            }
            i |= (1 << k);
        }
        return true;
    }
    //最短无序连续子数组
    public int findUnsortedSubarray(int[] nums) {
        int left = -1;
        int right = -1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            if(nums[i] < max) {
                right = i;
            }else {
                max = nums[i];
            }

            if(nums[n-i-1] > min) {
                left = n-i-1;
            }else {
                min = nums[n-i-1];
            }
        }
        return left == -1 ? 0 : right - left + 1;
    }
    //螺旋矩阵2
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        int k = 1;
        int left = 0;
        int right = n-1;
        int top = 0;
        int bottom = n-1;
        while(left <= right && top <= bottom) {
            //第一行
            for(int i = left; i <= right; i++) {
                ret[top][i] = k++;
            }
            //最后一列
            for(int i = top+1; i <= bottom; i++) {
                ret[i][right] = k++;
            }
            //最后一行
            for(int i = right-1; i >= left; i--) {
                ret[bottom][i] = k++;
            }
            //第一列
            for(int i = bottom-1; i > top; i--) {
                ret[i][left] = k++;
            }
            left++;
            top++;
            right--;
            bottom--;
        }
        return ret;
    }
}
